package List$Stack$queue;

import java.util.Stack;

/**
 * 最小栈问题
 * 当栈pop元素出来的时候，能够立马计算出剩余元素的最小值
 * 这就需要每当有新元素push进来的时候，都记录当前一步栈的最小值，出栈同时将最小值也同时出栈
 */
public class MinStack {
    Stack<Integer> stack; // 存储原始栈
    Stack<Integer> minValue; // 辅助栈，存储最小值的栈
    public MinStack() {
        stack = new Stack<>();
        minValue = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        // 如果存储最小值的栈为空，则直接将该值压入栈
        if (minValue.size() == 0) {
            minValue.push(val);
        }else {
            minValue.push(minValue.peek() <= val ? minValue.peek() : val);
        }
    }

    public void pop() {
        // 出栈操作，原始栈和辅助栈都执行出栈操作
        stack.pop();
        minValue.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minValue.peek();
    }
}
